package binaryTree;

import java.util.ArrayDeque;

public class FanZhuanBinaryTree {

    public TreeNode invertTree(TreeNode root) {
        if (root==null){
            return null;
        }
        swap(root);
        invertTree(root.left);
        invertTree(root.right);
        return  root;
    }
    public  void swap( TreeNode root){
        TreeNode temp = root.left;
        root.left=root.right;
        root.right=temp;
    }

    public  void  bianli(TreeNode root){
        if (root==null){
            return;
        }
        System.out.println(root.val);
        bianli(root.left);
        bianli(root.right);
    }

    public TreeNode invertTree1(TreeNode root) {
        if (root == null) {return null;}
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.poll();
                swap(node);
                if (node.left != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);
            }
        }
        return root;
    }




    public static void main(String[] args) {
     TreeNode root= new TreeNode(5);
      TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2=new TreeNode(1);
       TreeNode treeNode3 = new TreeNode(2);
 TreeNode treeNode4= new TreeNode(6);
        root.left=treeNode1;
        root.right=treeNode3;
        treeNode1.left=treeNode2;
        treeNode3.right=treeNode4;

        FanZhuanBinaryTree fanZhuanBinaryTree = new FanZhuanBinaryTree();
        fanZhuanBinaryTree.invertTree(root);
  fanZhuanBinaryTree.bianli(root);


    }
}
